//
//  98. 验证二叉搜索树.swift
//  手撕code
//
//  Created by xiaoZuDeMeng on 2024/3/6.
//

import Foundation

//https://leetcode.cn/problems/validate-binary-search-tree/
//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
//
//有效 二叉搜索树定义如下：
//
//节点的左子树只包含 小于 当前节点的数。
//节点的右子树只包含 大于 当前节点的数。
//所有左子树和右子树自身必须也是二叉搜索树。
//
//
//示例 1：
//
//
//输入：root = [2,1,3]
//输出：true
//示例 2：
//
//
//输入：root = [5,1,4,null,null,3,6]
//输出：false
//解释：根节点的值是 5 ，但是右子节点的值是 4 。
//
//
//提示：
//
//树中节点数目范围在[1, 104] 内
//-231 <= Node.val <= 231 - 1

func isValidBST(_ root: TreeNode?) -> Bool {
    return isValidBST(root, lower: Int.min, upper: Int.max)
}

func isValidBST(_ node: TreeNode?, lower: Int, upper: Int) -> Bool {
    guard let node = node else {
        return true
    }
    
    if node.val <= lower || node.val >= upper {
        return false
    }
    
    return isValidBST(node.left, lower: lower, upper: node.val) && isValidBST(node.right, lower: node.val, upper: upper)
}
